#include <iostream>
#include <stack>
#include <stdio.h>
#define N 9
using namespace std;
typedef struct {
    int ord;
    int r;
    int c;
    int dir;
}node;
void showMaze(int maze[N][N]) {
    static int a = 1;
    cout << a++ << endl;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            printf("%3d", maze[i][j]);
        }
        cout << endl;
    }
    cout << endl;
}
bool mazePath(int maze[N][N], int src_r, int src_c, int end_r, int end_c) {
    int cur_r = src_r, cur_c = src_c;
    stack<node*> s;
    int curstep = 1;
    do {
        if (!maze[cur_r][cur_c]) { // 当前位置可以是可以通过，为0
            maze[cur_r][cur_c] = curstep;
            showMaze(maze);
            node* cur = new node;
            cur->r = cur_r;
            cur->c = cur_c;
            cur->ord = curstep;
            cur->dir = 0;
            s.emplace(cur);
            if (cur_r == end_r && cur_c == end_c) {
                return true;
            }
            ++cur_c;
            ++curstep;
        } else { // maze[cur_r][cur_c]不通
            if (!s.empty()) {
                node* cur = s.top();
                s.pop();
                cur_r = cur->r;
                cur_c = cur->c;
                
                // 下面的while和if只有一个能执行
                while (cur->dir == 4 && !s.empty()) { // 若方向全遍历完，下面if也不会执行
                    maze[cur_r][cur_c] = -2;
                    node* curt = s.top();
                    s.pop();
                    cur_r = curt->r;
                    cur_c = curt->c;
                    --curstep;
                    showMaze(maze);
                    cur = curt;
                }
                if (cur->dir < 4) { // 栈顶位置的块还有未遍历方向
                    ++cur->dir;
                    s.emplace(cur);
                    switch (cur->dir) {
                        case 1: {++cur_r;break;}
                        case 2: {--cur_c;break;}
                        case 3: {--cur_r;break;}
                    }
                }
            }
        }
    } while (!s.empty());
    return false;
}
int main(void) {
    // 0为路，2为墙
    int maze[N][N] = {
        {-1, -1, -1, -1, -1, -1, -1, -1, -1},
        {-1,  0, -1,  0, -1, -1,  0, -1, -1},
        {-1,  0,  0,  0, -1, -1,  0, -1, -1},
        {-1,  0, -1,  0,  0, -1,  0, -1, -1},
        {-1,  0, -1, -1,  0,  0,  0, -1, -1},
        {-1,  0, -1, -1,  0, -1,  0, -1, -1},
        {-1,  0,  0, -1,  0,  0,  0, -1, -1},
        {-1, -1,  0,  0, -1, -1, -1,  0, -1},
        {-1, -1, -1, -1, -1, -1, -1, -1, -1}
    };

    bool ans = mazePath(maze, 1, 1, 7, 3);

    cout << ans << endl;

    return 0;
}